
import java.util.Arrays;
import java.util.Stack;

public class Test {
    /**
     * 直接插入排序
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     */
    public void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if(arr[j] > tmp){
                    arr[j+1] = arr[j];
                }else{
                    break;
                }
            }
            arr[j+1] = tmp;
        }
    }
    /**
     * 冒泡排序
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     */
    public void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            boolean flg = true;
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j] > arr[j+1]){
                    int tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                    flg = false;
                }
            }
            if(flg){
                break;
            }
        }
    }

    /**
     * 希尔排序 - 直接排序的优化版
     * 时间复杂度：O(n^1.3)~O(1^1.5)
     * 空间复杂度：O(1)
     * 稳点性：不稳定
     */
    public void shellSort(int[] arr){
        int gap = arr.length;
        while(gap > 1){
            gap /= 2;
            for (int i = gap; i < arr.length; i++) {
                int tmp = arr[i];
                int j = i - gap;
                for (; j >= 0; j -= gap) {
                    if(arr[j] > tmp){
                        arr[j+gap] = arr[j];
                    }else{
                        break;
                    }
                }
                arr[j+gap] = tmp;
            }
        }
    }

    /**
     * 选择排序
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     */
    public void selectSort(int[] arr){
        int end = arr.length;
        while(end > 1){
            int maxIndex = 0;
            for (int i = 1; i < end; i++) {
                if(arr[maxIndex] < arr[i]){
                    maxIndex = i;
                }
            }
            swap(arr,maxIndex,end-1);
            end--;
        }
    }
    public void selectSort1(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[minIndex] > arr[j]){
                    minIndex = j;
                }
            }
            swap(arr,minIndex,i);
        }
    }
    public void selectSort2(int[] arr){
        int left = 0;
        int right = arr.length-1;
        while(left < right){
            int minIndex = left;
            int maxIndex = right;
            for (int i = left+1; i <= right; i++) {
                if(arr[maxIndex] < arr[i]){
                    maxIndex = i;
                }
                if(arr[minIndex] > arr[i]){
                    minIndex = i;
                }
            }
            swap(arr,left,minIndex);
            if(left == maxIndex){
                maxIndex = minIndex;
            }
            swap(arr,right,maxIndex);
            left++;
            right--;
        }
    }
    public void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    /**
     * 快排
     * 时间复杂度：O(nlogN)
     * 空间复杂度：O(logN)
     * 稳定性：不稳定
     */
    //Hoare法
    public void quickSort(int[] arr, int left, int right){
        if(left > right) return;

        //int mid = midOfThree(arr,left,right);
        //swap(arr,mid,left);

        //swap(arr,left,mid);
        int div = partition(arr, left, right);
        quickSort(arr,left,div-1);
        quickSort(arr,div+1,right);
    }
    public int midOfThree(int[] arr, int left, int right){
        int mid = left + (right-left)/2;
        if(arr[left] < arr[right]){
            if(arr[left] > arr[mid]){
                return left;
            }else if(arr[mid] > arr[right]){
                return right;
            }else {
                return mid;
            }
        }else {
            if(arr[left] < arr[mid]){
                return left;
            }else if(arr[right] > arr[mid]){
                return right;
            }else {
                return mid;
            }
        }
    }
    public int partition(int[] arr, int left, int right){
        int tmp = left;
        int key = arr[left];
        while(left < right){
            while(left < right && arr[right] >= key){
                right--;
            }
            while(left < right && arr[left] <= key){
                left++;
            }
            swap(arr,left,right);
        }
        swap(arr,tmp,left);
        return left;//or right
    }
    //挖坑法
    public int partition1(int[] arr, int left, int right){
        int tmp = arr[left];
        while(left < right){
            while(left < right && arr[right] >= tmp){//=必须有 ， 必须是right先走
                right--;
            }
            arr[left] = arr[right];
            while(left < right && arr[left] <= tmp){
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }
    //指针法
    public int partition2(int[] arr, int left, int right){
        int prev = left;
        int cur = left + 1;
        while(cur <= right){
            if(arr[cur] < arr[left] && (++prev) != cur ){
                swap(arr,prev,cur);
            }
            cur++;
        }
        swap(arr,left,prev);
        return prev;
    }
    //非递归写法
    public void quickSortNor(int[] arr, int left, int right){
        Stack<Integer> ret = new Stack<>();
        ret.push(left);
        ret.push(right);
        while(!ret.empty()){
            right = ret.pop();
            left = ret.pop();
            int div = partition(arr,left,right);
            if(left + 1 < div){
                ret.push(left);
                ret.push(div-1);
            }
            if(right-1 > div){
                ret.push(div+1);
                ret.push(right);
            }
        }
    }

    /**
     * 归并排序
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(n)
     * 稳定
     */
    public void mergeSort(int[] arr, int left, int right){
        if(left >= right) return;
        int mid = left + (right - left)/2;
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1,right);
        merge(arr,left,right,mid);
    }
    public void merge(int[] arr, int left, int right, int mid){
        int s1 = left;
        int s2 = mid+1;
        int k = 0;
        int[] tmp = new int[right-left+1];
        while(s1 <= mid && s2 <= right){
            if(arr[s1] <= arr[s2]){
                tmp[k++] = arr[s1++];
            }else{
                tmp[k++] = arr[s2++];
            }
        }
        while(s1 <= mid){
            tmp[k++] = arr[s1++];
        }
        while (s2 <= right){
            tmp[k++] = arr[s2++];
        }
        for (int i = 0; i < tmp.length; i++) {
            arr[i+left] = tmp[i];
        }
    }
    //非递归
    public void mergeSortNor(int[] arr){
        int gap = 1;
        while(gap < arr.length){
            for (int i = 0; i < arr.length; i+=2*gap) {
                int left = i;//相邻两段子数组的开始和末位下标 [left,mid] [mid+1,right]
                int mid = left + gap -1;
                int right = mid + gap;
                if(mid >= arr.length){//说明只有前面一段数组
                    mid = arr.length - 1;
                }
                if(right >= arr.length){//说明后面的子数组数量少
                    right = arr.length-1;
                }
                merge(arr,left,right,mid);
            }
            gap *= 2;
        }
    }
    public static void main(String[] args) {
        int[] array = {6,2,4,10,8,5,1,9};
        Test test = new Test();
        //test.mergeSortNor(array);
        //test.quickSortNor(array,0, array.length-1);
        test.quickSort(array,0, array.length-1);
        //test.shellSort(array);
        //test.bubbleSort(array);
        //test.insertSort(array);
        System.out.println(Arrays.toString(array));
    }
}


class BinarySearchTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root = null;

    public boolean search(int val) {
        TreeNode cur = root;
        while (cur != null) {
            if(cur.val < val) {
                cur = cur.right;
            }else if(cur.val > val) {
                cur = cur.left;
            }else {
                return true;
            }
        }
        return false;
    }

    public void insert(int val) {
        if(root == null){
            root = new TreeNode(val);
            return;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null){
            parent = cur;
            if(cur.val < val){
                cur = cur.right;
            }else if(cur.val > val){
                cur = cur.left;
            }else {
                return;
            }
        }
        if(parent.val < val){
            parent.right = new TreeNode(val);
        }else {
            parent.left = new TreeNode(val);
        }
    }


}